1. Field of the Invention
The present invention relates to a method and an apparatus for decoding an error correcting code, and more specifically, it relates to a method and an apparatus for decoding an error correcting code such as a BCH (Bose-Chaudhuri-Hocquenghem) code employed for detecting and correcting a bit error in received data in a digital data transmission system such an automobile telephone system, a cordless telephone or satellite broadcasting.
2. Description of the Prior Art
In transmission of digital data, a bit error is generally caused by deterioration in the S-N ratio or distortion of the transmission system. In a general method of coping with such a bit error, redundant bits having error correcting ability (hereinafter referred to as error correcting bits) are previously added to original information bits, to be subjected to transmission. On the data sink side, a bit error position is detected on the basis of the received error correcting bits, to be corrected. Among such error correcting codes, the BCH code, having high error correcting ability with respect to length (bit number) of the correcting bits, is widely employed for transmission of a control signal in an automobile telephone system or a cordless telephone in Japan or U.S., or in a digital data transmission system such as PCM (pulse Code Modulation) audio broadcasting by satellite.
Description is briefly made on detection/correction of a bit error in transmission data through the BCH code. On the data source side, error correcting bits are obtained on the basis of original information bits and a predetermined generator polynominal G(X) to be added to the original information bits, and subjected to transmission. On the data sink side, a received signal train V(X) is divided by the above described generator polynominal, thereby to find the remainder term S(X) thereof. This remainder term S[X) is hereinafter referred to as a syndrome. Presence/absence of a bit error is judged on the basis of the syndrome S(X), to detect the error position. Then, bit error correction is performed by inverting the value of the bit corresponding to the detected error position.
FIG. 1 typically illustrates basic structure for data transmission in an automobile telephone system employing such a BCH code. Referring to FIG. 1, each terminal 1 is connected to a base station 3 through an exchange 2. High frequency radio communication in a scope of 800 to 900 MHz is performed between the base station 3 and a mobile station 4, while, in particular, control between both the stations such as origination, paging and channel switching is performed by transmission of digital signals.
For example, in an automobile telephone system according to the specification of Nippon Telegraph and Telephone Corp., original information bits are transmitted with addition of the BCH code in transmission of digital signals for such control. More specifically, according to the specification of Nippon Telegraph and Telephone Corp., a first control signal from the base station 3 to the mobile station 4 and a second control signal from the mobile station 4 to the base station 3 both employ the BCH code obtained on the basis of the original information bits and a generator polynominal G(X) =X.sup.11 +X.sup.9 +X.sup.7 +X.sup.6 +X.sup.5 +X +1. On the data source side, a bit train of zeros in number equal to the degree of the generator polynominal [i.e., 11) is added to the original information bits so as to follow the least significant bit thereof. Then, the original information bits with the bit train of zeros are divided by the generator polynominal G(X), to find the remainder R(X). This remainder R(X) is added to the original information bits so as to follow the least significant bit thereof, to be subjected to transmission.
According to the above described specification of Nippon Telegraph and Telephone Corp., for example, the code length n of the digital control signal thus transmitted is 19 bits, the length m of the information bits therein is 8 bits while minimum distance of codes is 7. Thus, it is possible to provide three-bit error correcting ability, while erroneous correction may be caused in this case. Therefore, the specification of Nippon Telegraph and Telephone Corp. is restricted only to single-bit error correcting ability (primary correction), to improve ability for preventing erroneous correction.
In order to perform primary correction of the received data to which the BCH code is added, the received signal train V[X) is generally divided by the generator polynominal G(X) to first obtain the remainder term, i.e., the syndrome S(X). If the value of the syndrome S(X) is zero, i.e., when the received signal train V(X) is exactly divisible by the generator polynominal G(X), a judgement is made that no bit error is caused. On the other hand, if the value of the syndrome S(X) is not zero, i.e., when the received signal train V(X) is not divided out by the generator polynominal G(X), a judgement is made that a single-bit error or a multiple-bit error is caused in the process of data transmission. A ROM table storing previously calculated values of bit error positions corresponding to syndrome values in occurrence of single-bit errors is prepared such that the corresponding bit error position can be obtained from the ROM table with the address of the obtained value of the syndrome S(X). Such a technique is disclosed in, for example, an article by K. Koga et al., entitled "Bit Error Rate Reduction Performance of BCH Codes and Self-Orthogonal Convolutional Codes", Transactions of IECE Japan, February 1979, Vol. J62-B, No. 2.
According to the above described method, however, capacity required for the ROM is 2.sup.k bytes assuming that k represents the degree of the generator polynominal (in the case of the code length of within 255 bits. If the code length exceeds 255 bits, the capacity is further increased). In the above described specification of Nippon Telegraph and Telephone Corp., the degree of the generator polynominal is 11, and hence 2.sup.11 =2048 bytes are required as the capacity for the ROM. On the other hand, the code length of the received signal is 19 bits, and hence the number of effective error positions in occurrence of a primary error is 19.
Thus, according to the conventional error correcting method as described above, the required ROM capacity is too far increased as compared with the number of the primary error correcting positions, to deteriorate availability of the ROM.
On the other hand, if and when the generator polynominal G(X) can be factored as G(X) =G.sub.I (X).multidot.G.sub.2 (X), a primary error can be judged by the following method. Syndromes S.sub.1 (X) and S.sub.2 (X) for primitive polynominals G.sub.1 (X) and G.sub.2 (X) found by factoring the generator polynominal G(X) are first obtained. A single-bit error position l in a received signal train V(X) is read out from a first ROM table with the address of the syndrome S.sub.1 (X). Then, a syndrome S.sub.2 '(X) corresponding to the single-bit error position l is read out from a second ROM table to be compared with the syndrome S.sub.2 (X) actually calculated from an operation of V(X)/G.sub.2 (X) The primary error is judged on the basis of the comparison. According to this method, capacity for the ROM can be significantly reduced. Such a system for decoding a BCH code is disclosed in Japanese Patent Laying-Open Gazette No. 288524/1986.
However, in the case of a generator polynominal which cannot be factored, such as a generator polynominal G(X) =X.sup.11 +X.sup.9 +X.sup.7 +X.sup.6 +X.sup.5 +X +1 employed in an automobile telephone system according to the above described specification of Nippon Telegraph and Telephone Corp., the above described method cannot be employed, so that capacity for the ROM cannot be reduced.